/*
947.移除最多的同行或同列石头  https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/
2024/10/12 中等
*/
class Solution {
public:
    // 存储每个石头所属集合的代表元素
    vector<int> parent;
    // 计算可以移除的石子的最大数量
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        // 初始化 parent 数组，每个石头初始时自己是一个集合
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
        // 使用哈希表记录行和列对应的石头索引
        unordered_map<int, int> rowMap;
        unordered_map<int, int> colMap;
        // 遍历所有石头
        for (int i = 0; i < n; ++i) {
            int row = stones[i][0];
            int col = stones[i][1];
            // 如果当前行已经有石头在哈希表中
            if (rowMap.find(row)!= rowMap.end()) {
                // 合并当前石头和该行已有的石头所在的集合
                unionSets(i, rowMap[row]);
            } else {
                // 将当前石头的索引存入哈希表，作为该行的代表石头
                rowMap[row] = i;
            }
            // 如果当前列已经有石头在哈希表中
            if (colMap.find(col)!= colMap.end()) {
                // 合并当前石头和该列已有的石头所在的集合
                unionSets(i, colMap[col]);
            } else {
                // 将当前石头的索引存入哈希表，作为该列的代表石头
                colMap[col] = i;
            }
        }
        int count = 0;
        // 统计集合的数量
        for (int i = 0; i < n; ++i) {
            if (parent[i] == i) {
                count++;
            }
        }

        // 返回可以移除的石子数量，即总石头数减去集合数量
        return n - count;
    }
    // 查找元素的代表元素，路径压缩
    int findParent(int x) {
        if (parent[x]!= x) {
            parent[x] = findParent(parent[x]);
        }
        return parent[x];
    }
    // 合并两个集合
    void unionSets(int x, int y) {
        int parentX = findParent(x);
        int parentY = findParent(y);
        if (parentX!= parentY) {
            parent[parentX] = parentY;
        }
    }
};